#include <vector>

using namespace std;

class Solution {
public:

    // 152. 乘积最大子数组
    // https://leetcode.cn/problems/maximum-sum-circular-subarray/
    int maxSubarraySumCircular(vector<int>& nums) {
        int sum = 0;
        int n = nums.size();
        vector<int> f(n+1), g(n+1);
        for (auto num : nums)
            sum += num;

        for (int i = 1; i<=n; ++i)
        {
            f[i] = min(nums[i-1], f[i-1] + nums[i-1]);
            g[i] = max(nums[i-1], g[i-1] + nums[i-1]);
        }

        int min_sum = *min_element(f.begin()+1, f.end());
        int max_sum = *max_element(g.begin()+1, g.end());


        if (min_sum == sum) // 防止 sum - min = 0 > max
            return max_sum;
        else
            return max(sum - min_sum, max_sum);
    }

    // 152. 乘积最大子数组
    // https://leetcode.cn/problems/maximum-product-subarray/
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n+1), g(n+1);
        f[0] = g[0] = 1;

        for (int i = 1; i<=n; ++i)
        {
            f[i] = max(nums[i-1], max(f[i-1]*nums[i-1], g[i-1]*nums[i-1]));
            g[i] = min(nums[i-1], min(g[i-1]*nums[i-1], f[i-1]*nums[i-1]));
        }

        return *max_element(f.begin() + 1, f.end());
    }
};